/**
 * 
 */
package algorithm.passed;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author xyyi
 *
 */
public class WordLadderII {

	/**
	Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

	Only one letter can be changed at a time
	Each intermediate word must exist in the dictionary
	For example,

	Given:
	start = "hit"
	end = "cog"
	dict = ["hot","dot","dog","lot","log"]

	Return

	[
	["hit","hot","dot","dog","cog"],
	["hit","hot","lot","log","cog"]
	]
	Note:

	All words have the same length.
	All words contain only lowercase alphabetic characters.
	
	http://www.cnblogs.com/shawnhue/archive/2013/06/05/leetcode_126.html
	 */
	public ArrayList<ArrayList<String>> findLadders(String start, String end,
	        HashSet<String> dict) {

		HashSet<String> visited = new HashSet<String>();
		LinkedList<String> queue = new LinkedList<String>();
		HashMap<String, LinkedList<String>> backtrace = new HashMap<String, LinkedList<String>>();
		queue.offer(start);
		StringBuffer sb = new StringBuffer();

		while (!queue.isEmpty()) {
			for (int i = 0; i < queue.size(); i++) {
				visited.add(queue.get(i));
			}

			for (int length = queue.size(); length >= 1; length--) {
				String word = queue.poll();
				sb.append(word);
				for (int i = 0; i < start.length(); i++) {
					char currChar = word.charAt(i);
					for (char c = 'a'; c <= 'z'; c++) {
						if (c != currChar) {
							sb.setCharAt(i, c);
							String newWord = sb.toString();
							if (!visited.contains(newWord)
							        && dict.contains(newWord)) {
								queue.offer(newWord);
								updateBacktrace(backtrace, newWord, word);
							}
						}
						sb.setCharAt(i, currChar);
					}
				}
				sb.setLength(0);
			}
			if (backtrace.containsKey(end)) {
				break;
			}
		}

		ArrayList<ArrayList<String>> paths = new ArrayList<ArrayList<String>>();
		if (backtrace.containsKey(end))
			buildPath(end, backtrace, paths, new LinkedList<String>());

		return paths;
	}

	// DFS
	private void buildPath(String word,
	        HashMap<String, LinkedList<String>> backtrace,
	        ArrayList<ArrayList<String>> paths, LinkedList<String> buffer) {

		buffer.addFirst(word);
		if (backtrace.get(word) == null) {
			paths.add(new ArrayList<String>(buffer));
		} else {
			LinkedList<String> list = backtrace.get(word);
			for (String str : list) {
				buildPath(str, backtrace, paths, buffer);
			}
		}
		buffer.removeFirst();
	}

	private void updateBacktrace(HashMap<String, LinkedList<String>> backtrace,
	        String word, String preWord) {
		if (backtrace.containsKey(word)) {
			//if (!backtrace.get(word).contains(preWord))
			backtrace.get(word).add(preWord);
		} else {
			LinkedList<String> list = new LinkedList<String>();
			list.add(preWord);
			backtrace.put(word, list);
		}
	}

	/**
	 * Word Ladder CareerCup 150
	 */
	public List<String> findOneLadder(String start, String end,
	        HashSet<String> dict) {
		LinkedList<String> result = new LinkedList<String>();
		Queue<String> queue = new LinkedList<String>();
		HashMap<String, String> backtrack = new HashMap<String, String>();
		HashSet<String> visited = new HashSet<String>();
		start = start.toLowerCase();
		end = end.toLowerCase();
		queue.offer(start);
		visited.add(start);

		while (!queue.isEmpty()) {
			String word = queue.poll();
			char[] chars = word.toCharArray();
			for (int i = 0; i < word.length(); i++) {
				char curr = chars[i];
				for (char c = 'a'; c <= 'z'; c++) {
					if (c != curr) {
						chars[i] = c;
						String newWord = new String(chars);
						if (newWord.equals(end)) {
							result.addFirst(newWord);
							while (word != null) {
								result.addFirst(word);
								word = backtrack.get(word);
							}
							return result;
						}

						if (!visited.contains(newWord)
						        && dict.contains(newWord)) {
							queue.offer(newWord);
							visited.add(newWord);
							backtrack.put(newWord, word);
						}
					}
				}
			}
		}

		return result;
	}

	public WordLadderII() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		WordLadderII wlii = new WordLadderII();
		String start = "red";
		String end = "tax";
		HashSet<String> dict = new HashSet<String>();
		dict.add("ted");
		dict.add("tex");
		dict.add("red");
		dict.add("tax");
		dict.add("tad");
		dict.add("den");
		dict.add("rex");
		dict.add("pee");
		wlii.findLadders(start, end, dict);
		//"red", "tax", ["ted","tex","red","tax","tad","den","rex","pee"]
	}

}
